package com.myown.algorithm;

import com.sun.org.apache.xml.internal.security.algorithms.Algorithm;

/**
 * 斐波那契数列 <p>
 *
 * 黄金分割散列 <p>
 *
 * f(0) = 0, n=0 <p>
 * f(1) = 1, n=1 <p>
 * f(n) + f(n+1) = f(n+2), n>1 <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017.02.23 15:46
 */
public class Fibonacci {

    /**
     * 递归法求取斐波那契数列 <p>
     *
     * 前30：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
     * 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229 <p>
     *
     * 时间复杂度：O(n) <p>
     *
     * @param index 索引
     * @return 索引指向的斐波那契数列
     */
    public static final int fibonacci(int index) {
        if (index == 1) {
            return 0;
        }
        if (index == 2) {
            return 1;
        }
        int f1 = 0, f2 = 1, f3 = 1;
        for (int i = 2; i < index; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    public static void main(String[] args) {
        int size = 30;
        for (int i = 1; i <= size; i++) {
            System.out.print(Fibonacci.fibonacci(i));
            if (i != size) {
                System.out.print(", ");
            }
        }
    }

}
